package java学习.游族网络;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * **************
 * 项目名称: 蓝桥杯-Java学习 <br/>
 * 文件名称:  <br/>
 * 文件描述: 这里添加您的类文件描述，说明当前文件要包含的功能。 <br/>
 * 文件创建：刘世锦Lenovo <br/>
 * 创建时间: 2022/10/16 <br/>
 *
 * @version v1.0 <br/>
 * @update [序号][日期YYYY-MM-DD][更改人姓名][变更描述]<br/>
 * *************
 */
public class 三数之和 {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型一维数组
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> threeSum (int[] nums) {
        // write code here
        Arrays.sort(nums);
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        for (int i = 0; i < nums.length; i++) {
            if (nums[i]>0){
                return res;
            }
            // 对a进行去重
            if (i>0&&nums[i]==nums[i-1]){
                continue;
            }
            int left = i+1;
            int right = nums.length-1;
            while (left<right){
                int sum = nums[left]+nums[right]+nums[i];
                if (sum>0){
                    right--;
                }else if (sum<0){
                    left++;
                }else {
                    while (left<right&&nums[left]==nums[left+1]){
                        left++; // 对 b去重
                    }
                    while (left<right&&nums[right]==nums[right-1]){
                        right--; // 对c去重
                    }
                    ArrayList<Integer> list = new ArrayList<>(Arrays.asList(nums[i],nums[left],nums[right]));
                    res.add(list);
                    left++; right--;
                }
            }
        }
        return res;
    }
}
